//
//  CloneGraph.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/8/12.
//  Copyright © 2020 WangYonghe. All rights reserved.
//

import UIKit

/*
 
 133. 克隆图
 给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

 图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

 class Node {
     public int val;
     public List<Node> neighbors;
 }
  

 测试用例格式：

 简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

 邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

 给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

  

 示例 1：
 1 -- 2
 |    |
 3 -- 4
 
 输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
 输出：[[2,4],[1,3],[2,4],[1,3]]
 解释：
 图中有 4 个节点。
 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。


 示例 2：

    1
 
 输入：adjList = [[]]
 输出：[[]]
 解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。
 
 
 示例 3：

 输入：adjList = []
 输出：[]
 解释：这个图是空的，它不含任何节点。
 
 
 示例 4：

    1 -- 2

 输入：adjList = [[2],[1]]
 输出：[[2],[1]]
  

 提示：

 节点数不超过 100 。
 每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。
 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
 图是连通图，你可以从给定节点访问到所有节点。
 */
 
public class Node:NSObject{
    public var val: Int
    public var neighbors: [Node?]
    public init(_ val: Int) {
        self.val = val
        self.neighbors = []
    }
}


class CloneGraph: NSObject {
    
    /*
     1.使用哈希表存储所有原节点和克隆的节点。哈希表中的key表示原节点，value对应key节点克隆后的节点。
     2.从给定的节点开始遍历图。如果某个节点已经被访问，则直接返回克隆图中对应的节点。
     3.如果当前访问的节点不在哈希表中，则克隆该节点，并存储在哈希表中。
        注意：在进入递归之前，必须先创建克隆节点并保存在哈希表中。如果不保证这种顺序，可能会在递归过程中遇到同一个节点，导致死循环。
     4.递归调用每个节点的邻节点。每个节点递归调用的次数等于邻节点的数量，每一次调用返回其对应邻节点的克隆节点，
    最终返回这些克隆邻节点的列表，将其对应放入对应克隆节点的邻节点列表中。这样就可以克隆给定节点和其邻节点。
     */
    
    /*------------dfs深度优先遍历-----------*/
    var hashMap:[Node:Node] = [:]
    func cloneGraphDFS(_ node: Node?) -> Node? {
        guard node != nil else {
            return node
        }
        
        //如果该节点已经访问过，则直接取出对应的克隆节点作为返回值
        if hashMap[node!] != nil {
            return hashMap[node!]
        }
        
        //克隆节点
        let newNode = Node.init(node!.val)
        
        //将新的节点储存在哈希表
        hashMap[node!] = newNode
        
        //遍历原节点的邻居并更新克隆节点的邻居列表
        for neighNode in node!.neighbors{
            newNode.neighbors.append(self.cloneGraphDFS(neighNode))
        }
        
        return newNode
    }
    
    
    /*------------bfs广度优先遍历-----------*/
    func cloneGraphBFS(_ node: Node?) -> Node? {
        guard node != nil else {
            return node
        }
        //维护一个队列
        var queue:[Node] = []
        queue.append(node!)
        //克隆第一个节点并加入哈希表
        let newNode = Node.init(node!.val)
        hashMap[node!] = newNode
        
        //bfs
        while queue.isEmpty == false {
            //取出头节点
            let first = queue.removeFirst()
            //遍历该节点的邻节点
            for neighborNode in first.neighbors{
                if hashMap[neighborNode!] == nil {
                    let newNode = Node.init(neighborNode!.val)
                    hashMap[neighborNode!] = newNode
                    queue.append(neighborNode!)
                }
                //更新当前节点的邻居列表
                hashMap[first]!.neighbors.append(hashMap[neighborNode!])
            }
        }
        return hashMap[node!]
    }
}
